package main

import (
	"fmt"
	"hash/crc32"
	"sort"
)


var nodes = make(map[string][]int) // 真实节点
var positions = make([]int, 0)
var positionsNodes = make(map[int]string) // 虚拟节点
var virtualNodeCount = 16 // 每个节点对应虚拟节点数量

func newConsistentHash(nodes []string) *consistentHash{
	ch := new(consistentHash)
	for _, node := range nodes {
		ch.addNode(node)
	}
	return ch
}

type consistentHash struct {
}

func (ch *consistentHash) hash(str string) int {
	// 把字符串转为32位符号整数
	return int(crc32.ChecksumIEEE([]byte(str)))
}

func (ch *consistentHash) lookup(key string) string {
	point := ch.hash(key)

	// 先取圆环上最小的一个节点,当成结果
	var current = positions[0]

	// 循环获取相近的节点 todo 二分法查找
	for _, pos := range positions {
		if point <= pos {
			current = pos
			break
		}
	}

	return positionsNodes[current]
}

func (ch *consistentHash) addNode(node string) {
	if _, ok := nodes[node]; ok {
		panic("node exist")
	}

	// 添加节点和虚拟节点
	for i := 0; i < virtualNodeCount; i++ {
		pos := ch.hash(fmt.Sprintf("%s_%d", node, i))
		positions = append(positions, pos)
		positionsNodes[pos] = node
		nodes[node] = append(nodes[node], pos)
	}

	// 重新排序
	sort.Ints(positions)
}

func main() {
	conns := make([]string, 3)
	conns[0] = "a"
	conns[1] = "b"
	conns[2] = "c"

	ch := newConsistentHash(conns)
	fmt.Println(nodes)
	fmt.Println(positions)
	fmt.Println(positionsNodes)
	fmt.Println(ch.lookup("abc"))
	fmt.Println(ch.lookup("123"))
	fmt.Println(ch.lookup("456"))
}